#include<stdio.h>
#include<stdlib.h>

// using a circular-double ll as booking
typedef struct IINode IINode;
struct IINode
{
    int* p;
    int psize;
    IINode* forward;
    IINode* next;
};
IINode* IINode_Intp(int* p, int psize)
{
    IINode* pnode = (IINode*)malloc(sizeof(IINode));
    pnode->p = p;
    pnode->psize = psize;
    pnode->forward = pnode;
    pnode->next = pnode;
    return pnode;
}
void link_node(IINode* *H, IINode* p)
{
    if(*H == NULL) 
    {
        *H = p;
        p->next = p;
        p->forward = p;
    }
    else
    {
        p->next = *H;
        p->forward = (*H)->forward;
        (*H)->forward->next = p;
        (*H)->forward = p;
    }
    return; 
}

void solve(int* state, int* nums, int cpos, int choice, int Size, IINode* *booking, int* bSize)
{
    state[cpos] = choice;
    if(cpos >= Size-1)
    {
        int* p = (int*)malloc(sizeof(int)*Size);
        int psize=0;
        for(int i = 0,j=0; i<=cpos;++i)
        {
            if(state[i]){p[j++] = nums[i];psize++;}
        }
        IINode* pnode = IINode_Intp(p,psize);
        link_node(booking, pnode);
        (*bSize)++;
        return;
    }
    cpos++;
    solve(state,nums,cpos,0,Size,booking,bSize);
    solve(state,nums,cpos,1,Size,booking,bSize);
}


int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    int* state = (int*)malloc(sizeof(int)*numsSize);
    IINode* booking = NULL;
    int cpos = 0; *returnSize=0;
    solve(state,nums,cpos,0,numsSize,&booking,returnSize);
    solve(state,nums,cpos,1,numsSize,&booking,returnSize);
    // copy booking to a 2d arr
    int** res = (int**)malloc(sizeof(int*)*(*returnSize));
    *(returnColumnSizes)=(int*)malloc(sizeof(int)*(*returnSize));
    IINode* tmp = booking;
    int count = 0;
    do
    {
        res[count] = (int*)malloc(sizeof(int)*tmp->psize);
        for(int i=0; i<tmp->psize;++i)res[count][i] = tmp->p[i];
        (*returnColumnSizes)[count] = tmp->psize;
        tmp = tmp->next; count++;
    } while (tmp!=booking);
    return res;
}


int main(int argc, char const *argv[])
{
    const int NUMS = atoi(argv[1]);
    int nums[NUMS];for(int i=0;i<NUMS;++i)nums[i]=i;
    int returnSize;
    int* returnColumnSizes;
    int** res = subsets(nums,NUMS,&returnSize,&returnColumnSizes);

    for(int i=0;i<returnSize;++i)
    {
        if(returnColumnSizes[i]==0) printf(","); 
        else
        {
            for(int j=0;j<returnColumnSizes[i];++j)
            {
                printf("%d,",res[i][j]);
            }
        }
        printf("\n");
    }
    
    return 0;
}
